// Copyright (c) ycq_work@163.com

/**
 * @Author: ycq_work@163.com
 * @DATE: 2023/7/15
*/

#ifndef MXGLIST_H
#define MXGLIST_H

namespace mxg::stl
{
template<typename T>
struct node
{
    T data;

    node<T> *_nextPtr;                  // 后继
    node<T> *_prevPtr;                  // 前驱
};

template<typename T>
class list
{
private:
    node<T> *_head;                     // 头指针
    node<T> *_tail;                     // 尾部指针
    int _size{};                        // 数据量
    int _capacity{999999999};           // 容量正常情况不限制 为一个很大的数

public:
    list();

    // 有固定容量的list表
    // explicit list(int capacity);

    // 构造函数
    explicit list(T& data);

    explicit list(const T &data);

    explicit list(T &&data);

    // 虚构函数
    ~list();

    /// 检查list是否为空
    [[nodiscard]] bool empty();

    // 检查list是否满 一般不用, 特殊情况
    [[nodiscard]] bool checkFull();

    // 对链表操作
    // 改变容器中可存储元素的个数
    void resize(int capacity);

    void clear();

    void push_back(const T& data);

    void push_back(T& data);

    void push_back(T&& data);

    void pop_back();

    void insert(int index, T &data);

    void insert(int index, const T &data);

    void insert(int index, const T &&data);

    void insert(int index, const list<T> &other);

    void emplace(int index, T &data);

    void emplace(int index, const T &data);

    void emplace(int index, const T &&data);

    void emplace(int index, const list<T> &other);

    // 获取
    [[nodiscard]] int size();

    [[nodiscard]] T& front();

    [[nodiscard]] T& back();

    [[nodiscard]] list<T>& operator=(list<T> other);
private:
    // 声明一个新链表
    void try_init();

    void delete_node(int pos);

    void delete_node(int begin, int end);

};

template<typename T>
list<T>::list()
{
    this->_head = nullptr;
    this->_tail = nullptr;
    this->_size = 0;
}

template<typename T>
list<T>::list(T& data)
{
    list(static_cast<T&>(data));
}

template<typename T>
list<T>::list(const T &data)
{
    try_init();
    this->_head->data = data;
}

template<typename T>
list<T>::list(T &&data)
{
    try_init();
    this->_head->data = static_cast<T&>(data);
}

template<typename T>
list<T>::~list()
{
    delete_node(0, this->_size);
}

template<typename T>
bool list<T>::empty()
{
    return this->_size == 0;
}

template<typename T>
bool list<T>::checkFull()
{
    return this->_size >= this->_capacity;
}

template<typename T>
void list<T>::resize(int capacity)
{
    _capacity = capacity;
}

template<typename T>
void list<T>::clear()
{
    // 保留头结点
    delete_node(0, _size);
    if(this --> _head)
    {

    }

    delete_node(1, _size);
    this->_head->data = -99999;
    this->_size = 0;
}

template<typename T>
void list<T>::push_back(const T &data)
{
    push_back(static_cast<T&>(data));
}

template<typename T>
void list<T>::push_back(T &data)
{
    if(this->_size >= this->_capacity)
    {
        // 链表已达到容量上限
        return;
    }

    auto* newNode = new node<T>(data);

    if(_head == nullptr)
    {
        _head = newNode;
        _tail = newNode;
    }
    else
    {
        _tail->_nextPtr = newNode;
        newNode->_prevPtr = _tail;
        _tail = newNode;
    }

    _size++;
}

template<typename T>
void list<T>::push_back(T &&data)
{
    push_back(data);
}

template<typename T>
void list<T>::pop_back()
{
    delete_node(this->_size);
}

template<typename T>
void list<T>::insert(int index, T &data)
{
    // 超出容量
    if(_size >= _capacity)
    {
        return;
    }

    // 位置不合理
    if(index < 0 || index > _size)
    {
        return;
    }

    auto* newNode = new node<T>(data);
    // 插入节点为头部
    if(index == 0)
    {
        newNode->_nextPtr = _head;
        if(_head != nullptr)
        {
            _head->_prevPtr = newNode;
        }
        _head = newNode;
        if(_tail == nullptr)
        {
            _tail = newNode;
        }
    }
    else if(index == _size)
    {
        // 在尾部插入节点
        _tail->_nextPtr = newNode;
        newNode->_prevPtr = _tail;
        _tail = newNode;
    }
    else
    {
        // 中间
        auto* currNode = _head;
        for(int i = 0; i < index - 1; ++i)
        {
            currNode = currNode->_nextPtr;
        }

        newNode->_nextPtr = currNode->_nextPtr;
        newNode->_prevPtr = currNode;
        currNode->_nextPtr->_prevPtr = newNode;
        currNode->_nextPtr = newNode;
    }

    _size++;
}

template<typename T>
void list<T>::insert(int index, const T &data)
{
    insert(index, static_cast<T&>(data));
}

template<typename T>
void list<T>::insert(int index, const T &&data)
{
    insert(index, data);
}

template<typename T>
void list<T>::insert(int index, const list<T> &other)
{
    if(index < 0 || index > _size)
    {
        // 位置错误
        return;
    }

    if(_size + other._size > _capacity)
    {
        // 超出容量
        return;
    }

    node<T>* newHead = nullptr;
    node<T>* newTail = nullptr;
    node<T>* current = other._head;

    // 复制other list
    while(current != nullptr)
    {
        auto* newNode = new node<T>(current->data);
        if(newHead == nullptr)
        {
            newHead = newNode;
            newTail = newNode;
        }
        else
        {
            newTail->_nextPtr = newNode;
            newNode->_prevPtr = newTail;
            newTail = newNode;
        }
        current = current->_nextPtr;
    }

    // 插入链表中
    if(index == 0)
    {
        // 头结点
        newTail->_nextPtr = _head;
        if(_head != nullptr)
        {
            _head->_prevPtr = newTail;
        }
        _head = newHead;
        if(_tail == nullptr)
        {
            _tail = newTail;
        }
    }
    else if(index == _size)
    {
        _tail->_nextPtr = newHead;
        newHead->_prevPtr = _tail;
        _tail = newTail;
    }
    else
    {
        // 中间
        current = _head;
        for(int i = 0; i < index - 1; ++i)
        {
            current = current->_nextPtr;
        }
        newTail->_nextPtr = current->_nextPtr;
        newTail->_nextPtr->_prevPtr = newTail;
        current->_nextPtr = newHead;
        newHead->_prevPtr = current;
    }

    _size += other._size;
}

template<typename T>
void list<T>::emplace(int index, T &data)
{

}

template<typename T>
void list<T>::emplace(int index, const T &data)
{

}

template<typename T>
void list<T>::emplace(int index, const T &&data)
{

}

template<typename T>
void list<T>::emplace(int index, const list<T> &other)
{

}

template<typename T>
int list<T>::size()
{
    return this->_size;
}

template<typename T>
T &list<T>::front()
{
    return this->_head->data;
}

template<typename T>
T &list<T>::back()
{
    return this->_tail->data;
}

template<typename T>
list<T> &list<T>::operator=(list<T> other)
{

}


template<typename T>
void list<T>::try_init()
{
    _head = new node<T>();
    _tail = _head;
    _size = 0;
}

template<typename T>
void list<T>::delete_node(int pos)
{
    if(pos < 0 || pos > _size)
    {
        return;
    }

    node<T>* prevNode = nullptr;
    node<T>* currNode = _head;

    for(int i = 0; i < pos; ++i)
    {
        prevNode = currNode;
        currNode = currNode->_nextPtr;
    }

    node<T> *nextNode = currNode->_nextPtr;
    delete currNode;

    if(prevNode == nullptr)
    {
        _head = nextNode;
    }
    else
    {
        prevNode->_nextPtr = nextNode;
    }

    currNode = nextNode;
    this->_size--;

    _tail = (pos == _size - 1) ? prevNode : _tail;
}

template<typename T>
void list<T>::delete_node(int begin, int end)
{
    if(begin < 0 || end >= _size || begin > end)
    {
        return;
    }

    // 定位到区间开始位置的前一个位置
    node<T>* prevNode = nullptr;
    node<T>* currNode = _head;
    for(int i = 0; i <= begin; ++i)
    {
        prevNode = currNode;
        currNode = currNode->_nextPtr;
    }

    for(int i = begin; i <= end; ++i)
    {
        node<T> *nextNode = currNode->_nextPtr;
        delete currNode;
        // 如果删除的节点是头结点, 更新头结点
        if(prevNode == nullptr)
        {
            _head = nextNode;
        }
        // 不是则修改上一个节点的指针
        else
        {
            prevNode->_nextPtr = nextNode;
        }

        currNode = nextNode;
        this->_size--;
    }
    // 更新尾指针位置
    _tail = (end == _size - 1) ? prevNode : _tail;
}

}// namespace mxg::stl

#endif //MXGLIST_H